package com.lmk.dsa.struct.graph;

import java.util.ArrayList;
import java.util.List;
import com.lmk.dsa.struct.commons.Edge;

/**
 * 稠密图，使用邻接矩阵实现
 * @author LaoMake
 * @since 1.0
 */
public class DenseGraph extends Graph {
	
	/** 边的集合：邻接矩阵 */
	private Edge[][] matrix;
	
	public DenseGraph(int n) {
		super(n);
		matrix = new Edge[n][n];
	}
	
	public DenseGraph(Object[] array) {
		super(array);
		matrix = new Edge[n][n];
	}
	
	/**
	 * 获取邻接矩阵
	 * @return
	 */
	public Edge[][] getMatrix() {
		return this.matrix;
	}

	@Override
	public List<Edge> adjoinEdge(int index) {
		Edge[] edges = matrix[index];
		List<Edge> adjoinEdges = new ArrayList<>();
		for(Edge edge : edges){
			if(edge != null){
				adjoinEdges.add(edge);
			}
		}
		return adjoinEdges;
	}

	@Override
	public List<Integer> adjoinVertex(int index) {
		Edge[] edges = matrix[index];
		List<Integer> vertexes = new ArrayList<>();
		for(Edge edge : edges){
			if(edge != null){
				vertexes.add(edge.to);
			}
		}
		return vertexes;
	}



	@Override
	public void addEdge(int from, int to, int weight) {
		assert from >= 0 && from < n : "from 越界";
		assert to >= 0 && to < n : "to 越界";
		assert from != to : "起始索引不能与目标索引相同";
		assert weight > 0 : "权值必须大于0";

		
		if(!hasEdge(from, to)) { // 消除平行边
			matrix[from][to] = new Edge(from, to, weight);
			edgeList.add(new Edge(from, to, weight));

			if(!directed) {
				matrix[to][from] = new Edge(to, from, weight);
				edgeList.add(new Edge(to, from, weight));
			}
			m++;
		}
	}

	@Override
	public Integer weight(int from, int to) {
		Edge edge = matrix[from][to];
		return edge != null ? edge.weight : null;
	}

	@Override
	public boolean hasEdge(int from, int to) {
		assert from >= 0 && from < n : "from 越界";
		assert to >= 0 && to < n : "to 越界";
		assert from != to : "起始索引不能与目标索引相同";

		return matrix[from][to] != null;
	}

	@Override
	public void show() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				System.out.print(weight(i, j) + ", ");
			}
			System.out.println();
		}
	}
}
